/**
 * \file List.h
 * \brief List definition and declaration class
 * \author Edouard ROGE
 * \date 8 September 2012
 */
#ifndef _LIST_
#define _LIST_

#include <stdlib.h>
#include "Core/Memory/HeapObject.h"

/**
 * \class List
 * \brief List class with template, similar to std::list<T>
 */
template < class T >
class List
{
public:

	/**
	 * \class Node
	 * \brief List Node
	 */
	class Node : public HeapObject
	{
	public:

		/**
		 * \fn Node();
		 * \brief Default constructor
		 */
		Node();

		/**
		 * \fn Node(const T & _element);
		 * \param _element node object
		 * \brief Constructor with parameter
		 */
		Node(const T & _element);

		/**
		 * \fn ~Node();
		 * \brief Destructor
		 */
		~Node();

		/**
		 * \fn Node * Next();
		 * \return next element
		 * \brief retrieve the next element to the current one
		 */
		Node * Next();

		/**
		 * \fn Node * Previous();
		 * \return previous element
		 * \brief retrieve the previous element to the current one
		 */
		Node * Previous();

		/**
		 * \fn const Node * Next() const;
		 * \return next element
		 * \brief retrieve the next element to the current one
		 */
		const Node * Next() const;

		/**
		 * \fn const Node * Previous() const;
		 * \return previous element
		 * \brief retrieve the previous element to the current one
		 */
		const Node * Previous() const;

		/**
		 * \fn void SetValue(const T & _value);
		 * \param _value new value for the object node
		 * \brief Set node object value
		 */
		void SetValue(const T & _value);

		/**
		 * \fn const T & GetValue() const;
		 * \return value of the node object
		 * \brief Set node object value
		 */
		const T & GetValue() const;

		/**
		 * \fn operator T & ();
		 * \brief cast operator
		 */
		operator T & ();

		/**
		 * \fn operator const T & () const;
		 * \brief cast operator
		 */
		operator const T & () const;

	private:

		/** template object */
		T m_object;

		/** preivous node */
		Node * m_pPrevious;

		/** next node */
		Node * m_pNext;

		friend class List<T>;
	};

	/** List<T>::Iterator */
	typedef Node *		Iterator;

	/** List<T>::ConstIterator */
	typedef const Node*	ConstIterator;

	/**
	 * \fn List();
	 * \brief Default constructor
	 */
	List();

	/**
	 * \fn List(const List<T> & _tList);
	 * \brief Copy constructor
	 */
	List(const List<T> & _tList);

	/**
	 * \fn ~List();
	 * \brief Destructor
	 */
	~List();

	/**
	 * \fn void Clear();
	 * \brief Clear the list, remove all the elements
	 */
	void Clear();

	/**
	 * \fn void Insert(const T & _element);
	 * \param _element element to insert
	 * \brief insert an element at the end of the list
	 */
	void Insert(const T & _element);

	/**
	 * \fn void Insert(Iterator _it, const T & _element);
	 * \param _it place where the element is inserted
	 * \param _element element to insert
	 * \brief insert an element to the position given by the iterator
	 */
	void Insert(Iterator _it, const T & _element);

	/**
	 * \fn Iterator Remove(Iterator _it);
	 * \param _it place to remove an element
	 * \brief remove an element from the list
	 */
	Iterator Remove(Iterator _it);

	/**
	 * \fn void Insert(List<T>::ConstIterator _it, const T & _element);
	 * \param _it place where the element is inserted
	 * \param _element element to insert
	 * \brief insert an element to the position given by the iterator
	 */
	void Insert(typename List<T>::ConstIterator _it, const T & _element);

	/**
	 * \fn List<T>::ConstIterator Remove(List<T>::ConstIterator _it);
	 * \param _it place to remove an element
	 * \return an iterator to the next removed element
	 * \brief remove an element from the list
	 */
	typename List<T>::ConstIterator Remove(typename List<T>::ConstIterator _it);

	/**
	 * \fn Iterator Begin();
	 * \return a pointer on the first element
	 * \brief Begin iterator
	 */
	Iterator Begin();

	/**
	 * \fn Iterator End();
	 * \return a pointer on the last element
	 * \brief End iterator
	 */
	Iterator End();

	/**
	 * \fn ConstIterator Begin() const;
	 * \return a pointer on the first element
	 * \brief Begin iterator
	 */
	ConstIterator Begin() const;

	/**
	 * \fn ConstIterator End() const;
	 * \return a pointer after the last element
	 * \brief End iterator
	 */
	ConstIterator End() const;

	/**
	 * \fn Iterator Find(const T & _element);
	 * \param _element element to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in list
	 */
	Iterator Find(const T & _element);

	/**
	 * \fn ConstIterator Find(const T & _element) const;
	 * \param _element element to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in list
	 */
	ConstIterator Find(const T & _element) const;

	/**
	 * \fn List<T> & operator = (const List<T> & _List);
	 * \param _List list to copy
	 * \return (*this) with new values
	 * \brief operator =
	 */
	List<T> & operator = (const List<T> & _List);
	/**
	 * \fn template < class S > friend bool operator == (const List<S> & _List1, const List<S> & _List2);
	 * \param _List1 list1
	 * \param _List2 list2
	 * \return true if list1 is equal to list2
	 * \brief operator ==
	 */
	template < class S > friend bool operator == (const List<S> & _List1, const List<S> & _List2);

	/**
	 * \fn template < class S > friend bool operator != (const List<S> & _List1, const List<S> & _List2);
	 * \param _List1 list1
	 * \param _List2 list2
	 * \return true if list1 is not equal to list2
	 * \brief operator !=
	 */
	template < class S > friend bool operator != (const List<S> & _List1, const List<S> & _List2);

private:

	/** Root list element */
	Node * m_pRoot;

	/** Node  */
	Node * m_pListEnd;

};

template <class T>
List<T>::Node::Node()
: m_pPrevious(NULL), m_pNext(NULL)
{
}

template <class T>
List<T>::Node::Node(const T & _element)
: m_object(_element), m_pPrevious(NULL), m_pNext(NULL)
{
}

template <class T>
const typename List<T>::Node * List<T>::Node::Next() const
{
	return m_pNext;
}

template <class T>
const typename List<T>::Node * List<T>::Node::Previous() const
{
	return m_pPrevious;
}

template <class T>
typename List<T>::Node * List<T>::Node::Next()
{
	return m_pNext;
}

template <class T>
typename List<T>::Node * List<T>::Node::Previous()
{
	return m_pPrevious;
}

template <class T>
void List<T>::Node::SetValue(const T & _value)
{
	m_object = _value;
}

template <class T>
const T & List<T>::Node::GetValue() const
{
	return m_object;
}

template <class T>
List<T>::Node::operator T &()
{
	return m_object;
}

template <class T>
List<T>::Node::operator const T &() const
{
	return m_object;
}

template <class T>
List<T>::Node::~Node()
{
	m_pNext=NULL;
	m_pPrevious=NULL;
}

template <class T>
List<T>::List()
: m_pRoot(NULL), m_pListEnd(new Node)
{
	m_pRoot = m_pListEnd;
	m_pListEnd->m_pNext = m_pListEnd;
	m_pListEnd->m_pPrevious = m_pListEnd;
}

template <class T>
List<T>::List(const List<T> & _tList)
: m_pRoot(NULL), m_pListEnd(new Node)
{
	m_pRoot = m_pListEnd;
	m_pListEnd->m_pNext = m_pListEnd;
	m_pListEnd->m_pPrevious = m_pListEnd;

	for(List<T>::ConstIterator it=_tList.Begin(); it!=_tList.End(); it=it->Next())
	{
		Insert(it->GetValue());
	}
}

template <class T>
List<T>::~List()
{
	Clear();
	delete m_pListEnd;
}

template <class T>
void List<T>::Clear()
{
	while(Begin()!=End())
		Remove(Begin());
}

template <class T>
void List<T>::Insert(const T & _element)
{
	Insert(End(), _element);
}

template <class T>
void List<T>::Insert(Iterator _it, const T & _element)
{
	if(!_it)
		return;

	Node * pNode = new Node(_element);
	Node * pPrev = NULL;

	if(Begin()==End())
	{
		m_pRoot = pNode;
	}

	pPrev = _it->m_pPrevious;
	pNode->m_pNext  = _it;
	_it->m_pPrevious = pNode;
	pPrev->m_pNext  = pNode;
	pNode->m_pPrevious = pPrev;
}

template <class T>
void List<T>::Insert(ConstIterator _it, const T & _element)
{
	if(!_it)
		return;

	Node * pNode = new Node(_element);
	Node * pPrev = NULL;

	if(Begin()==End())
	{
		m_pRoot = pNode;
	}

	pPrev = _it->m_pPrevious;
	pNode->m_pNext  = _it;
	_it->m_pPrevious = pNode;
	pPrev->m_pNext  = pNode;
	pNode->m_pPrevious = pPrev;
}

template <class T>
typename List<T>::Iterator List<T>::Remove(Iterator _it)
{
	if(_it!=End())
	{
		Node * pPrev = (*_it).m_pPrevious;
		Node * pNext = (*_it).m_pNext;
		pPrev->m_pNext=pNext;
		pNext->m_pPrevious=pPrev;
		if(_it==Begin())
			m_pRoot = pNext;
		delete _it;
		return pNext;
	}

	return End();
}

template <class T>
typename List<T>::ConstIterator List<T>::Remove(ConstIterator _it)
{
	if(_it!=End())
	{
		Node * pPrev = (*_it).m_pPrevious;
		Node * pNext = (*_it).m_pNext;
		pPrev->m_pNext=pNext;
		pNext->m_pPrevious=pPrev;
		if(_it==Begin())
			m_pRoot = pNext;
		delete _it;
		return pNext;
	}

	return End();
}

template <class T>
typename List<T>::Iterator List<T>::Begin()
{
	return m_pRoot;
}

template <class T>
typename List<T>::Iterator List<T>::End()
{
	return m_pListEnd;
}

template <class T>
typename List<T>::ConstIterator List<T>::Begin() const
{
	return m_pRoot;
}

template <class T>
typename List<T>::ConstIterator List<T>::End() const
{
	return m_pListEnd;
}

template <class T>
typename List<T>::Iterator List<T>::Find(const T & _element)
{
	for(List<T>::Iterator it=Begin(); it!=End(); it=it->Next())
	{
		if((*it).GetValue()==_element)
			return it;
	}
	return End();
}

template <class T>
typename List<T>::ConstIterator List<T>::Find(const T & _element) const
{
	for(List<int>::Iterator it=Begin(); it!=End(); it=it->Next())
	{
		if((*it).GetValue()==_element)
			return it;
	}
	return End();
}

template <class T>
List<T> & List<T>::operator = (const List<T> & _List)
{
	Clear();
	m_pRoot = m_pListEnd;
	for(List<T>::Iterator it=_List.Begin(); it!=_List.End(); it=it->Next())
	{
		Insert((T)(*it));
	}
}

/**
 * \fn template < class S > bool operator == (const List<S> & _List1, const List<S> & _List2);
 * \param _List1 list1
 * \param _List2 list2
 * \return true if list1 is equal to list2
 * \brief operator ==
 */
template < class S >
bool operator == (const List<S> & _List1, const List<S> & _List2)
{
	typename List<S>::ConstIterator it1=_List1.Begin();
	typename List<S>::ConstIterator it2=_List2.Begin();
	while(it1!=_List1.End() && it2!=_List2.End())
	{
		if(it1->GetValue()!=it2->GetValue())
			return false;
		it1=it1->Next();
		it2=it2->Next();
	}

	return (it1==_List1.End() && it2==_List2.End());
}

/**
 * \fn template < class S > bool operator != (const List<S> & _List1, const List<S> & _List2);
 * \param _List1 list1
 * \param _List2 list2
 * \return true if list1 is not equal to list2
 * \brief operator !=
 */
template < class S >
bool operator != (const List<S> & _List1, const List<S> & _List2)
{
	return !(_List1==_List2);
}

#endif // _LIST_
